package com.example.algrithm.quicksort;

import java.util.Random;

public class QuickSort {

    private QuickSort() {
    }

    public static <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int p = partition(arr, l, r);
        sort(arr, l, p - 1);
        sort(arr, p + 1, r);
    }

    private static <E extends Comparable<E>> int partition(E[] arr, int l, int r) {
        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i].compareTo(arr[l]) < 0) {
                j++;
                swap(arr, j, i);
            }
        }
        swap(arr, l, j);
        return j;
    }

    public static <E extends Comparable<E>> void sort2(E[] arr) {
        sort2(arr, 0, arr.length - 1);
    }

    private static <E extends Comparable<E>> void sort2(E[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int p = partition2(arr, l, r);
        sort2(arr, l, p - 1);
        sort2(arr, p + 1, r);
    }

    private static <E extends Comparable<E>> int partition2(E[] arr, int l, int r) {
        // 优化点一，对于有序数组，如果一直取第一个元素作为标定点，算法会退化为O(n^2),改为取区间内随机的某个元素作为标定
        int p = new Random().nextInt(r - l + 1) + l;
        swap(arr, l, p);

        int j = l;
        for (int i = l + 1; i <= r; i++) {
            if (arr[i].compareTo(arr[l]) < 0) {
                j++;
                swap(arr, j, i);
            }
        }
        swap(arr, l, j);
        return j;
    }

    /**
     * 双开快排的第一种实现方式
     *
     * @param arr
     * @param <E>
     */
    public static <E extends Comparable<E>> void sort2ways(E[] arr) {
        sort2ways(arr, 0, arr.length - 1);
    }

    private static <E extends Comparable<E>> void sort2ways(E[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int p = partition2ways(arr, l, r);
        sort2ways(arr, l, p - 1);
        sort2ways(arr, p + 1, r);
    }

    private static <E extends Comparable<E>> int partition2ways(E[] arr, int l, int r) {
        int i = l + 1;
        int j = r;
        // 优化点一，对于有序数组，如果一直取第一个元素作为标定点，算法会退化为O(n^2),改为取区间内随机的某个元素作为标定
        int p = new Random().nextInt(r - l + 1) + l;
        swap(arr, l, p);
        E pVal = arr[l];
        for (; i <= j; ) {
            // arr[l+1 ... i] <= pval 且 arr[j ... r] >= pval
            // 如果 arr[i]
            if (pVal.compareTo(arr[i]) <= 0 && pVal.compareTo(arr[j]) >= 0) {
                swap(arr, i, j);
                i++;
                j--;
            } else {
                if (pVal.compareTo(arr[i]) > 0) {
                    i++;
                }
                if (pVal.compareTo(arr[j]) < 0) {
                    j--;
                }
            }
        }
        swap(arr, l, j);
        return j;
    }

    /**
     * 双路排序的第二种实现方式
     *
     * @param arr
     * @param <E>
     */
    public static <E extends Comparable<E>> void sort2ways2(E[] arr) {
        sort2ways2(arr, 0, arr.length - 1);
    }

    private static <E extends Comparable<E>> void sort2ways2(E[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int p = partition2ways2(arr, l, r);
        sort2ways(arr, l, p - 1);
        sort2ways(arr, p + 1, r);
    }

    private static <E extends Comparable<E>> int partition2ways2(E[] arr, int l, int r) {
        int i = l + 1;
        int j = r;
        // 优化点一，对于有序数组，如果一直取第一个元素作为标定点，算法会退化为O(n^2),改为取区间内随机的某个元素作为标定
        int p = new Random().nextInt(r - l + 1) + l;
        swap(arr, l, p);
        E pVal = arr[l];
        // 优化点二： 对于有大量元素相同的数组，尽量的将相同的元素分到两边，减少算法退化为O(n^2)的概率
        while (true) {
            while (i <= j && pVal.compareTo(arr[i]) > 0) {
                i++;
            }
            while (i <= j && pVal.compareTo(arr[j]) < 0) {
                j--;
            }
            if (i >= j) break;
            swap(arr, i, j);
            i++;
            j--;
        }
        swap(arr, l, j);
        return j;
    }

    /**
     * 三路快排：
     * 优化点：对于大量重复的元素，在 partition 的过程中避免重复处理，从而提升了算法效率
     *
     * @param arr
     * @param <E>
     */
    public static <E extends Comparable<E>> void sort3ways(E[] arr) {
        sort3ways(arr, 0, arr.length - 1);
    }

    private static <E extends Comparable<E>> void sort3ways(E[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int p = new Random().nextInt(r - l + 1) + l;
        swap(arr, l, p);
//        int p = partition3ways(arr, l, r);
        int lt = l;
        int gt = r + 1;
        int i = l + 1;
        while (i < gt) {
            if (arr[i].compareTo(arr[l]) < 0) {
                lt++;
                swap(arr, i, lt);
                i++;
            } else if (arr[i].compareTo(arr[l]) > 0) {
                gt--;
                swap(arr, i, gt);
            } else {
                i++;
            }
        }
        swap(arr, l, lt);
        sort2ways(arr, l, lt - 1);
        sort2ways(arr, gt, r);
    }

    private static <E extends Comparable<E>> void swap(E[] arr, int i, int j) {
        E tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        Integer[] arr = new Integer[]{7, 3, 4, 1, 7, 3, 7, 12, 2};
        QuickSort.sort3ways(arr);
        for (Integer item : arr) {
            System.out.println(item);
        }
    }
}
